/* Author: Mark Faust;   
 * Description: This file defines the two required functions for the branch predictor.
 */

#include "predictor.h"
#include <cstdlib>
#include <iostream>

unsigned THB[TARGET_HISTORY_BUFFER_SIZE];
unsigned THB_head_index = 0;
unsigned predictor_table[PREDICTOR_TABLE_SIZE];
int hash_predictor_table[HASH_NUM][HASH_PREDICTOR_TABLE_SIZE];
unsigned global_history;

unsigned path_num;
unsigned hash_num;
unsigned predictor_table_index;
unsigned hash_predictor_table_index;


using namespace std;

bool PREDICTOR::get_prediction( const branch_record_c* br, const op_state_c* os )
{
	bool prediction_result = true;

	unsigned prediction_counter;

	hash_num = getHashIndex(global_history);

	switch (hash_num)
	{
		case 0: path_num = 0; break;
		case 1: path_num = 1; break;
		case 2: path_num = 3; break;
		case 3: path_num = 7; break;
		case 4: path_num = 15; break;
		case 5: path_num = 31; break;
		default: cout << endl << hash_num << " is not a valid hash number" << endl;
	}

	//path_num = hash_num;

	predictor_table_index = getHashResult(path_num);

	prediction_counter = predictor_table[predictor_table_index];

	switch(prediction_counter & PREDICTOR_TAKEN)
	{
		case PREDICTOR_TAKEN	: prediction_result = TAKEN; 	break;

		case PREDICTOR_NOT_TAKEN: prediction_result = NOT_TAKEN; break;

		default: cout << endl << prediction_counter << " is not valid prediction counter number" << endl;
	}

	#ifdef DEBUG
		cout << " get_prediction()" << "  ";
		cout << " hash num: " << hash_num;
		cout << " pred_table_index: " << predictor_table_index;
		cout << " pred_cntr: " << prediction_counter;
		cout << " pred_result: " << prediction_result << endl;
	#endif

        return prediction_result;
}    
 
 
// Update the predictor after a prediction has been made.  This should accept
// the branch record (br) and architectural state (os), as well as a third
// argument (taken) indicating whether or not the branch was taken.
void PREDICTOR::update_predictor( const branch_record_c* br, const op_state_c* os, bool taken )
{
	bool is_mispredicted = true;

	unsigned prediction_counter;
	int hash_prediction_counter;


	// Update predictor table
	
	prediction_counter = predictor_table[predictor_table_index];

	#ifdef DEBUG
		cout << " update_predictor()" << "  ";
		cout << " taken: " << taken;
		cout << " glob_hist_bfor: " << global_history;
	#endif

	global_history <<= 1;

	#ifdef DEBUG
		cout << " glob_hist_aftr_shft: " << global_history;
	#endif

	if(taken)
	{
		global_history |= GLOBAL_HISTORY_UPDATE_MASK_T;

		switch(prediction_counter & PREDICTOR_TAKEN)
		{
			case PREDICTOR_TAKEN:	is_mispredicted = false; break;

			case PREDICTOR_NOT_TAKEN: is_mispredicted = true; break;

			default: cout << endl << prediction_counter << " is not valid prediction counter number" << endl;
		}

		if(prediction_counter < PREDICTOR_COUNTER_MAX)
			++prediction_counter;
	}
	else if(!taken)
	{
		global_history &= GLOBAL_HISTORY_UPDATE_MASK_N;

		switch(prediction_counter & PREDICTOR_TAKEN)
		{
			case PREDICTOR_TAKEN	: is_mispredicted = true; break;

			case PREDICTOR_NOT_TAKEN:  is_mispredicted = false; break;

			default: cout << endl << prediction_counter << " is not valid prediction counter number" << endl;
		}

		if(prediction_counter)
			--prediction_counter;
	}

	#ifdef DEBUG
		cout << " is_mispred: " << is_mispredicted;
		cout << " pred_cntr_aftr: " << prediction_counter << endl;
	#endif
	
	global_history &= GLOBAL_HISTORY_MASK;

	prediction_counter &= PREDICTOR_MASK;

	predictor_table[predictor_table_index] = prediction_counter;

	#ifdef DEBUG
		cout << " glob_hist_aftr: " << global_history;
	#endif

	// Update hash predictor table

	hash_prediction_counter = hash_predictor_table[hash_num][hash_predictor_table_index];

	#ifdef DEBUG
		cout << " hsh_prd_cntr_bfr: " << hash_prediction_counter ;
	#endif

	if(is_mispredicted && hash_prediction_counter > HASH_PREDICTOR_COUNTER_MIN)
		--hash_prediction_counter;
	else if(!is_mispredicted && hash_prediction_counter < HASH_PREDICTOR_COUNTER_MAX)
		++hash_prediction_counter;
	else;

	//hash_prediction_counter &= HASH_PREDICTOR_COUNTER_MASK;

	#ifdef DEBUG
		cout << " hsh_prd_cntr_aftr: " << hash_prediction_counter ;
	#endif

	hash_predictor_table[hash_num][hash_predictor_table_index] = hash_prediction_counter;
	

	// Update Target History Buffer in case the branch is conditional

	if(br->is_conditional)
	{
		THB_head_index = (++THB_head_index)%TARGET_HISTORY_BUFFER_SIZE;
		THB[THB_head_index] = br->branch_target & TARGET_HISTORY_BUFFER_MASK;

		#ifdef DEBUG
			cout << " THB_head_index: " << THB_head_index;
			cout << " br->trgt: " << br->branch_target;
		#endif	
	}

	
	#ifdef DEBUG
		cout << " THB[hd]_aftr: " << THB[THB_head_index];
		cout << endl << "------------------------------------------------------------------------------------------------" << endl;
	#endif


    /* replace this code with your own */
    /*    bool prediction = false;

    printf("%0x %0x %1d %1d %1d %1d ",br->instruction_addr,
                                      br->branch_target,br->is_indirect,br->is_conditional,
                                      br->is_call,br->is_return);
    if( br->is_conditional )
        prediction = true;
    return prediction;   // true for taken, false for not taken
    */
}

unsigned getHashIndex(unsigned global_history)
{
	unsigned i;
	int max_count = 0;

	hash_predictor_table_index = (global_history)%HASH_PREDICTOR_TABLE_SIZE;

	for(i = 0; i < HASH_NUM; ++i)
	{
		if(hash_predictor_table[i][hash_predictor_table_index] > max_count)
		{
			hash_num = i;
	
			max_count = hash_predictor_table[i][hash_predictor_table_index];
		}
	}

	#ifdef DEBUG
		cout << " 	getHashIndex()" << "  ";
		cout << " 	max_count: " << max_count << endl;
	#endif

	return hash_num;
}

unsigned getHashResult(unsigned PATH)
{
/*
	unsigned hash_result;

	if(PATH)
		hash_result = THB[PATH]^getHashResult(PATH-1);
	else
		hash_result = THB[PATH];
	
	return hash_result;
*/
	unsigned THB_next_lo, THB_next_hi, THB_next;
	unsigned hash_result = ~THB[(THB_head_index + TARGET_HISTORY_BUFFER_SIZE - PATH)&TARGET_HISTORY_BUFFER_SIZE];
	hash_result >>= 2;	
	hash_result &= TARGET_HISTORY_BUFFER_MASK;

	int i;

	#ifdef DEBUG
		cout << " 	getHashResult()" << "  ";
		cout << " 	~THB[]: " << hash_result;
	#endif


	for(i = PATH; i >= 0; --i)
	{
		THB_next = THB[(THB_head_index + TARGET_HISTORY_BUFFER_SIZE - i)&TARGET_HISTORY_BUFFER_SIZE];
		THB_next_lo = THB_next << i;
		THB_next_hi = THB_next >> (TARGET_HISTORY_BUFFER_SIZE - i);
		THB_next = THB_next_lo | THB_next_hi;
	
		hash_result ^= THB_next;
	}

	#ifdef DEBUG
		cout << " 	hash_result: " << hash_result << endl;
	#endif

	return hash_result;
}
